/**
 * @author VernHe
 * @date 2021年07月10日 15:00
 */
public class Solution_0337 {
    public int rob(TreeNode root) {
        int[] result = robInternal(root);
        return Math.max(result[0], result[1]);
    }

    private int[] robInternal(TreeNode node) {
        int[] result = new int[2];
        // 递归基
        if (null != node) {
            // 左子树
            int[] leftResult = robInternal(node.left);
            // 右子树
            int[] rightResult = robInternal(node.right);

            // 1. 如果当前节点不偷，则加上左右节点的最大值即可
            result[0] = Math.max(leftResult[0], leftResult[1]) + Math.max(rightResult[0], rightResult[1]);
            // 2. 如果当前节点偷，则在当前节点的基础上加上子节点不偷时对应的最大值
            result[1] = node.val + leftResult[0] + rightResult[0];
        }
        // 返回结果
        return result;
    }
}
